public class test3 {
    //力扣  LCR.06 重排链表
    public void reorderList(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //新建一个虚拟头结点
        ListNode head2 = new ListNode(0);
        ListNode cur=slow.next;
        slow.next = null;
        //cur为空说明链表遍历完毕
        //利用头插法，进行链表翻转
        while (cur!=null) {
            //记录一下，不然找不到了
            ListNode next=cur.next;
            cur.next =head2.next;
            head2.next = cur;
            cur = next;
        }
        ListNode ret = new ListNode(0);
        ListNode prev = ret;
        ListNode cur1 = head;
        ListNode cur2 = head2.next;
        while(cur1!=null  ){
            //合并第一个链表
            prev.next = cur1;
            prev = cur1;
            cur1 = cur1.next;
            //合并第二个链表
            if(cur2!=null){
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }

    }
}
